package leetcode.editor.cn;
 
/**
 * 一和零
 * @author qulq
 * @date 2024-07-24 19:45:41
 */
public class T474_OnesAndZeroes{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T474_OnesAndZeroes().new Solution();
	 }

	/**
	 * 01背包变种
	 * 到最后一个元素An，有两种情况，最优解中放An或不放An
	 * 不放：i个0，j个1的条件下，A0到An-1最大个数
	 * 放：i-（An的0的个数）、j-(An的1的个数)下，加上 1，得到最大个数
	 * f[i][j]:A0到An，0 1 个数分别为i和j下的最大个数
	 * f[i][j] = max(f[i][j], f[i - zeroNum][j - oneNum]+1)
	 */

// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
		int[][] dp = new int[m + 1][n + 1];
		int zeroNum, oneNum;
		for (String str : strs) {
			zeroNum = 0;
			oneNum = 0;
			for (char ch : str.toCharArray()) {
				if (ch == '0') {
					zeroNum++;
				} else {
					oneNum++;
				}
			}
			// 01背包的滚动数组，需要倒序遍历
			for (int i = m; i >= zeroNum; i--) {
				for (int j = n; j >= oneNum; j--) {
					dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
				}
			}
		}
		return dp[m][n];
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}